package everydayone.distributecandies;
/**
 * @Date 2020/03/05
 * @author 王光浩
 * @Thinking 使用数学方法进行计算。
 * @Analysis 时间复杂度O（n），空间复杂度O（m），n是轮数，m是num_people。
 */
public class MethodTwo {
    public int[] distributeCandies(int candies, int num_people) {
    	int total=(int)(Math.sqrt((float)2*candies+0.25)-0.5); //candies个糖果最多分的人数
    	int round=total/num_people;  //每个人最少一共需要重复分多少次
    	int left=total%num_people;  //下标小于left的人会多分一次（下标等于left的人将会获取剩下的）
    	int[] distribute=new int[num_people];  //最后结果
    	for(int i=0;i<num_people;i++) {
    		int candie=0;
    		if(i<left) {  //需要多分的人
    			candie=(i+1)*(round+1)+((round+1)*round*(num_people)/2);
    		}
    		else  //不需要多分的人
    			candie=(i+1)*(round)+(round*(round-1)*(num_people)/2);
    		candies-=candie;
    		distribute[i]=candie;
    	}
    	distribute[left]+=candies; //将剩余的给最后一个人
    	return distribute;    	
    }
}
